1. Field of the Invention
This invention relates to computer systems and, more particularly, to apparatus for addressing information in computer systems using virtual memory.
2. History of the Prior Art
Cache memories are used in computer systems to speed the overall operation of the system. The theory of a cache is that a system attains a higher speed by using a small portion of very fast random access memory (RAM) as a cache along with a larger amount of slower main memory random access memory. If data and instructions are called from main memory and placed in cache memory as they are required by the program, and if the system looks first to the cache memory when processing instructions and information to see if the information required is available there, then the system will usually find the information desired in the cache memory and will, consequently, operate at a speed as though it were made up mostly of high speed cache memory. This occurs because, statistically, information in any particular portion of a process which has just been used is more likely to be required immediately than is other information which has not been recently used.
There have been many forms of caching systems devised by the prior art. One way to design a cache memory used in a demand paged virtual memory system is to make the cache memory the same size as one of the main memory pages. When, in such a system, information is taken from main memory and placed in a cache memory, it may be stored in the same line of the cache memory as the line of the page from which it was accessed in main memory along with its virtual page address in main memory. If, on the other hand, the page size in main memory is a multiple of the cache size, then a few extra bits (depending on the multiple) are needed in the line address to specify the section of the page from which it came. In any case, each line of such a cache memory may come from any particular page of main memory so that lines lying adjacent each other in cache memory may have entirely different virtual page addresses. The virtual page address, a series of high order bits of the address, is usually stored as part of a tag field which in addition to the page address includes protection and control information such as whether the information is read or write protected and whether the information is valid. In a particular system, such a tag field may require approximately sixteen bits to represent the tag information.
A system uses the low order bits of the virtual address (the offset) to select the line in which information is stored in such a cache memory. Once the line is selected, the system determines whether the required information is in the cache memory (whether there is a hit) by looking for the correct virtual page address in the tag field of that line. If the page address in the tag field at the desired line in the cache memory matches the desired page address, then there is a hit; and the information in the cache memory may be used without the necessity of going to main memory. If the page address does not match, indicating that the information is not present in the cache memory, then the system must delay, go to main memory, replace the particular line in the cache memory, and finally operate on the information.
Of course, such a system does have disadvantages. When there is miss in the cache memory, several clock times may have passed before main memory is accessed for the missed information. In addition, the system uses quite a bit of address space in the cache memory to provide the tags to designate page addresses, protections, and the like. When multiplied by the lines of the cache memory, a substantial amount of memory space is required.
When the information sought is not contained in the cache memory, then it is necessary to find the information in physical memory and provide it to the cache memory for use. In such a case, the physical address of the information must be provided in order for the information to be obtained and written to the cache memory for use by the computer system. Normally this is accomplished in the following order. The virtual address is first used to address the cache memory (data or instruction cache) to first determine whether the information is available in the particular cache memory (whether a cache hit or a cache miss occurs). If a cache miss occurs, then the virtual address is directed to a set of often multiple-level page map tables which translate the virtual address to the physical address. Once the physical address is obtained, the information may be written into the particular cache memory and used by the central processing unit. It will be appreciated that such a process is relatively time-consuming and substantially slows the overall operation of the computer system.
To obviate this problem, certain computer systems have provided a buffer memory often called a translation look-aside buffer for storing both the virtual and comparable physical addresses of information recently utilized by the computer. Before going to the page map tables to translate the virtual address to a physical address, the system looks to the translation look-aside buffer to see if the virtual address is stored in that buffer. If it is, then the physical address of the information sought is immediately available, and the slower process of consulting the page map tables to determine the physical address is not necessary.
Computer systems often use multiple processors to allow various functions to be handled by other than the central processing unit (CPU) so that the speed of the overall system is increased. When multiple processors are used in a system, it is often advantageous to utilize an individual cache memory (or memories) with each processor in order to enhance the speed of operation of that processor. One special advantage offered by multiple cache memories in virtual memory systems is that the processors may share the same information because they may address the same physical memory. However, this ability of multiple processors to share the same information creates a data consistency problem because write operations which change the data in a particular cache memory associated with a particular processor may not be reflected in the physical memory shared by all of the processors or in other cache memories allowing other processors to share the same information. Consequently, multiprocessor computer systems utilizing virtual cache memories must provide some method of either indicating that information in a cache memory is stale or updating the stale information so that it will not be used by the system.
An additional problem occurs in systems using cache memory and translation look-aside buffers, there are sometimes cases where the page size used in virtual memory is not appropriate to the type of information being used. For example, if attempts are made to store very large arrays of scientific numbers in a virtual memory arrangement having a page size of sixty-four Kbytes, a translation look-aside buffer dealing with such information may have to deal with so many individual pages that it will begin thrashing and its advantage will not be realized. For this reason, it may often be desirable to effectively eliminate the virtual memory system. This may be done by allowing a system to select an extremely large page size such as sixteen Mbytes. However, translation look-aside buffers of the prior art adapted to operate with a first page size have not been able to operate with other page sizes of virtual memory.